package com.hanxiaozhang.no10leetcode.array;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 判断你是否能够到达最后一个位置。
 * 示例 1:
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳1步，从位置0到达位置1, 然后再从位置1跳3步到达最后一个位置。
 * <p>
 * 示例 2:
 * 输入: [3,2,1,0,4]
 * 输出: false
 *
 * 思路：
 * 1. 声明一个最远距离变量(farthest)
 * 2. 循环数组中每一个元素：
 *   - 当位置 小于 最远距离时，证明跳不过，返回false
 *   - 计算当前位置最远距离  ->  Math.max(farthest, i + nums[i]);
 *   - 最远距离 大于 数组长度 -1（终点） ，证明成功跳过
 *
 * @author hanxinghua
 * @create 2024/1/15
 * @since 1.0.0
 */
public class No55JumpGame {


    public static void main(String[] args) {

        int[] nums1 = {2, 3, 1, 1, 4};
        int[] nums2 = {3, 2, 1, 0, 4};
        // System.out.println(method1(nums1));
        System.out.println(method1(nums2));
    }


    /**
     * 方法1
     *
     * @param nums
     * @return
     */
    private static boolean method1(int[] nums) {
        // 最远距离
        int farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            // 当位置 小于 最远距离时，证明跳不过，返回false
            if (i > farthest) {
                return false;
            }
            // 计算当前位置最远距离
            farthest = Math.max(farthest, i + nums[i]);
            // 最远距离 大于 数组长度 -1（终点） ，证明成功跳过
            // -> 举例：数组长度为4时，只需要跳三步就到终点了。
            if (farthest > nums.length - 1) {
                return true;
            }
        }
        return false;
    }


}
